#include<iostream>
#include<vector>
using namespace std;

//46.全排列
//全局变量二维数组ret用来存放结果
vector<vector<int>> ret;
//全局变量数组check用来标记每个值是否用过
vector<bool> check;
//全局变量数组path用来存放每次的排列组合结果
vector<int> path;

void dfs(vector<int>& nums){
    //结束条件，当path数组的长度等于nums数组的长度时，将path数组添加到ret数组中
    if(path.size()==nums.size()){
        ret.push_back(path);
        return;
    }

    //循环
    for(int i=0;i<nums.size();i++){
        //剪枝操作
        //判断当前下标的数是否已经使用
        if(check[i]==false){
            path.push_back(nums[i]);
            check[i] = true;

            dfs(nums);

            //回溯操作
            //当从上一层函数调用返回时，要先去掉path数组的最后一个元素
            //并将check数组对应位置标记为未使用
            path.pop_back(nums[i]);
            check[i] = false;
        }
    }
}

vector<vector<int>> permute(vector<int>& nums){
    check.resize(nums.size());

    dfs(nums);
    return ret;
}

//78.子集
//全局变量二维数组
vector<vector<int>> ans;
vector<int> path;
//解法一
void dfs1(vector<int>& nums,int i){
    //结束条件，当下标i等于数组的长度时，将path数组存放到ans数组中
    if(i==nums.size()){
        ans.push_back(path);
        return;
    }

    //不选择nums[i]时
    dfs(nums, i + 1);

    //选择nums[i]时
    path.push_back(nums[i]);
    dfs(nums, i + 1);

    //回溯
    path.pop_back();
}
//解法二
void dfs2(vector<int>& nums,int pos){
    ret.push_back(path);

    for (int i = pos; i<nums.size();i++){
        path.push_back(nums[i]);
        dfs(nums, i + 1);
        //回溯
        path.pop_back();
    }
}
vector<vector<int>> subsets(vector<int>& nums){
    dfs1(nums, 0);
}

int main(){

    return 0;
}